class Solution:
    def rob(self, nums):
        if len(nums) == 1:
            return nums[0]
        def rob_line(num):
            n = len(num)
            if n == 1:
                return num[0]
            dp = [0] * n
            dp[0] = num[0]
            dp[1] = max(num[0], num[1])
            for i in range(2, n):
                dp[i] = max(dp[i-1], dp[i-2]+num[i])
            return dp[n-1]
        
        return max(rob_line(nums[:-1]), rob_line(nums[1:]))
if __name__ == '__main__':
    nums = [2,3,2]
    print(Solution().rob(nums))

# 由于首尾不能同时偷窃，我们可以将问题拆分成两个子问题：

# 偷窃第1间到第n-1间房屋（不偷最后一间）

# 偷窃第2间到第n间房屋（不偷第一间）

# 然后取两个子问题的最大值。